//////////////////////////////////////////////////////////////////////
//
// NO_SimpleHash.h: interface for the NO_SimpleHash class.
//
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
#ifndef NO_HASH_FUNC_H
#define NO_HASH_FUNC_H

//////////////////////////////////////////////////////////////////////////
template<class Key> inline unsigned long noGetHash(Key key)				{return (key%(1<<31));}
template<>			inline unsigned long noGetHash(unsigned char key)	{return (key);}
template<>			inline unsigned long noGetHash(unsigned short key)	{return (key);}
template<>			inline unsigned long noGetHash(unsigned long key)	{return (key);}
template<>			inline unsigned long noGetHash(signed char key)		{return ((unsigned long)key);}
template<>			inline unsigned long noGetHash(signed short key)	{return ((unsigned long)key);}
template<>			inline unsigned long noGetHash(signed long key)		{return ((unsigned long)key);}

/* The mixing step */
#define mix(a,b,c) \
{ \
	a=a-b;  a=a-c;  a=a^(c>>13); \
	b=b-c;  b=b-a;  b=b^(a<<8);  \
	c=c-a;  c=c-b;  c=c^(b>>13); \
	a=a-b;  a=a-c;  a=a^(c>>12); \
	b=b-c;  b=b-a;  b=b^(a<<16); \
	c=c-a;  c=c-b;  c=c^(b>>5);  \
	a=a-b;  a=a-c;  a=a^(c>>3);  \
	b=b-c;  b=b-a;  b=b^(a<<10); \
	c=c-a;  c=c-b;  c=c^(b>>15); \
}

/////////////////////////////////////////////////////////////////////////
template<> inline unsigned long noGetHash(std::string& s)
{
	const char* k = s.c_str();
	NO_UInt32 l = s.size();
	NO_UInt32 a,b,c;	/* the internal state */
	NO_UInt32 len = l;  /* how many key bytes still need mixing */
	
	a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
	c = 13466917;        /* variable initialization of internal state */
	
	while (len >= 12)
	{
		a=a+(k[0]+((NO_UInt32)k[1]<<8)+((NO_UInt32)k[2]<<16) +((NO_UInt32)k[3]<<24));
		b=b+(k[4]+((NO_UInt32)k[5]<<8)+((NO_UInt32)k[6]<<16) +((NO_UInt32)k[7]<<24));
		c=c+(k[8]+((NO_UInt32)k[9]<<8)+((NO_UInt32)k[10]<<16)+((NO_UInt32)k[11]<<24));
		mix(a,b,c);
		k = k+12; len = len-12;
	}
	
	c = c+l;
	switch(len)           
	{
	case 11: c=c+((NO_UInt32)k[10]<<24);
	case 10: c=c+((NO_UInt32)k[9]<<16);
	case 9 : c=c+((NO_UInt32)k[8]<<8);
	case 8 : b=b+((NO_UInt32)k[7]<<24);
	case 7 : b=b+((NO_UInt32)k[6]<<16);
	case 6 : b=b+((NO_UInt32)k[5]<<8);
	case 5 : b=b+k[4];
	case 4 : a=a+((NO_UInt32)k[3]<<24);
	case 3 : a=a+((NO_UInt32)k[2]<<16);
	case 2 : a=a+((NO_UInt32)k[1]<<8);
	case 1 : a=a+k[0];
	}
	mix(a,b,c);
	return c;
}

//////////////////////////////////////////////////////////////////////////
template<> inline unsigned long noGetHash(const std::string& s)
{
	const char* k = s.c_str();
	NO_UInt32 l = s.size();
	NO_UInt32 a,b,c;	/* the internal state */
	NO_UInt32 len = l;  /* how many key bytes still need mixing */
	
	a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
	c = 13466917;        /* variable initialization of internal state */
	
	while (len >= 12)
	{
		a=a+(k[0]+((NO_UInt32)k[1]<<8)+((NO_UInt32)k[2]<<16) +((NO_UInt32)k[3]<<24));
		b=b+(k[4]+((NO_UInt32)k[5]<<8)+((NO_UInt32)k[6]<<16) +((NO_UInt32)k[7]<<24));
		c=c+(k[8]+((NO_UInt32)k[9]<<8)+((NO_UInt32)k[10]<<16)+((NO_UInt32)k[11]<<24));
		mix(a,b,c);
		k = k+12; len = len-12;
	}
	
	c = c+l;
	switch(len)           
	{
	case 11: c=c+((NO_UInt32)k[10]<<24);
	case 10: c=c+((NO_UInt32)k[9]<<16);
	case 9 : c=c+((NO_UInt32)k[8]<<8);
	case 8 : b=b+((NO_UInt32)k[7]<<24);
	case 7 : b=b+((NO_UInt32)k[6]<<16);
	case 6 : b=b+((NO_UInt32)k[5]<<8);
	case 5 : b=b+k[4];
	case 4 : a=a+((NO_UInt32)k[3]<<24);
	case 3 : a=a+((NO_UInt32)k[2]<<16);
	case 2 : a=a+((NO_UInt32)k[1]<<8);
	case 1 : a=a+k[0];
	}
	mix(a,b,c);
	return c;
}

//////////////////////////////////////////////////////////////////////////
template<> inline unsigned long noGetHash(const char* k)
{
	NO_UInt32 l = strlen(k);
	NO_UInt32 a,b,c;	/* the internal state */
	NO_UInt32 len = l;  /* how many key bytes still need mixing */
	
	a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
	c = 13466917;        /* variable initialization of internal state */
	
	while (len >= 12)
	{
		a=a+(k[0]+((NO_UInt32)k[1]<<8)+((NO_UInt32)k[2]<<16) +((NO_UInt32)k[3]<<24));
		b=b+(k[4]+((NO_UInt32)k[5]<<8)+((NO_UInt32)k[6]<<16) +((NO_UInt32)k[7]<<24));
		c=c+(k[8]+((NO_UInt32)k[9]<<8)+((NO_UInt32)k[10]<<16)+((NO_UInt32)k[11]<<24));
		mix(a,b,c);
		k = k+12; len = len-12;
	}
	
	c = c+l;
	switch(len)           
	{
	case 11: c=c+((NO_UInt32)k[10]<<24);
	case 10: c=c+((NO_UInt32)k[9]<<16);
	case 9 : c=c+((NO_UInt32)k[8]<<8);
	case 8 : b=b+((NO_UInt32)k[7]<<24);
	case 7 : b=b+((NO_UInt32)k[6]<<16);
	case 6 : b=b+((NO_UInt32)k[5]<<8);
	case 5 : b=b+k[4];
	case 4 : a=a+((NO_UInt32)k[3]<<24);
	case 3 : a=a+((NO_UInt32)k[2]<<16);
	case 2 : a=a+((NO_UInt32)k[1]<<8);
	case 1 : a=a+k[0];
	}
	mix(a,b,c);
	return c;
}

//////////////////////////////////////////////////////////////////////////
template<> inline unsigned long noGetHash(char* k)
{
	NO_UInt32 l = strlen(k);
	NO_UInt32 a,b,c;	/* the internal state */
	NO_UInt32 len = l;  /* how many key bytes still need mixing */
	
	a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
	c = 13466917;        /* variable initialization of internal state */
	
	while (len >= 12)
	{
		a=a+(k[0]+((NO_UInt32)k[1]<<8)+((NO_UInt32)k[2]<<16) +((NO_UInt32)k[3]<<24));
		b=b+(k[4]+((NO_UInt32)k[5]<<8)+((NO_UInt32)k[6]<<16) +((NO_UInt32)k[7]<<24));
		c=c+(k[8]+((NO_UInt32)k[9]<<8)+((NO_UInt32)k[10]<<16)+((NO_UInt32)k[11]<<24));
		mix(a,b,c);
		k = k+12; len = len-12;
	}
	
	c = c+l;
	switch(len)           
	{
	case 11: c=c+((NO_UInt32)k[10]<<24);
	case 10: c=c+((NO_UInt32)k[9]<<16);
	case 9 : c=c+((NO_UInt32)k[8]<<8);
	case 8 : b=b+((NO_UInt32)k[7]<<24);
	case 7 : b=b+((NO_UInt32)k[6]<<16);
	case 6 : b=b+((NO_UInt32)k[5]<<8);
	case 5 : b=b+k[4];
	case 4 : a=a+((NO_UInt32)k[3]<<24);
	case 3 : a=a+((NO_UInt32)k[2]<<16);
	case 2 : a=a+((NO_UInt32)k[1]<<8);
	case 1 : a=a+k[0];
	}
	mix(a,b,c);
	return c;
}

#undef mix

//////////////////////////////////////////////////////////////////////////
template<class Key> inline bool noKeyCompare(Key k1,Key k2)					{return k1==k2;}
template<>			inline bool noKeyCompare(const char* s1,const char* s2)	{return strcmp(s1,s2)==0;}
template<>			inline bool noKeyCompare(char* s1,char* s2)				{return strcmp(s1,s2)==0;}

#endif

